/**
 * @author rongkai
 * @description:
 * @date 2021/3/31
 */
public class QuickSort {

    public void sort(int[] nums){
        sort(nums,0,nums.length-1);
    }

    private void sort(int[] nums,int low,int high){
        if (low >= high) {
            return;
        }
        int center = split(nums, low, high);
//        递归处理左边
        sort(nums,low,center);
//        递归处理右边
        sort(nums,center+1,high);
    }

    private int split(int[] nums,int low,int high){
        int left = low;
        int right = high-1;
        while (left < right){
            if (nums[left] < nums[high]){
                left++;
            }else if (nums[right] > nums[high]){
                right--;
            }else{
                swap(nums,left,right);
                left++;
                right--;
            }
        }
        if (nums[left] > nums[high]){
            swap(nums,left,high);
            print(nums);
            System.out.println();
            return left;
        }else{
            swap(nums,right,high);
            print(nums);
            System.out.println();
            return right;
        }
    }

    private void swap(int[] nums,int left,int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    private void print(int[] nums){
        for (int num : nums) {
            System.out.print(num+";");
        }
    }

    public static void main(String[] args) {

        QuickSort quickSort = new QuickSort();
        int[] nums = {2,5,1,6,10,4};
        quickSort.sort(nums);
        for (int num : nums) {
            System.out.print(num+";");
        }
    }
}
